package main

/*
	给定一个头节点为head的非空单链表，返回链表的中间节点，如果有两个中间节点，则返回第二个
*/

type ListNode struct{
	pData int
	Next *ListNode
}

func middleNode(head *ListNode) *ListNode{
	if(head.Next == nil){
		return head
	}
	//pTemp := head
	//len := 0
	////先求出链表长度
	//for{
	//	if(pTemp == nil){
	//		break
	//	}
	//	len++
	//	pTemp = pTemp.pNext
	//}
	//pFirst := head
	//pSecond := head
	////双指针，第一个比后面的先走(len-1)/2步
	//step := (len-1)>>1
	//for i:=0;i<step;i++{
	//	pFirst = pFirst.pNext
	//}
	//for{
	//	// 当第一个指针指向最后一个元素时，第二个指针所指的就是中间节点
	//	if(pFirst.pNext == nil){
	//		break
	//	}
	//	pFirst=pFirst.pNext
	//	pSecond=pSecond.pNext
	//}
	//如果求出了len就没必要使用快慢指针了，直接循环len/2
	//快慢指针，快指针一次移动2位，慢指针一次移动一位
	//快指针移动的条件时，当前节点和下一节点都不为空
	pFirst := head
	pSecond:= head
	for{
		if(pFirst == nil || pFirst.Next==nil){
			break
		}
		pFirst = pFirst.Next.Next
		pSecond = pSecond.Next
	}
	return pSecond
}
